package com.leecode;

import java.util.*;

/**
 * 15. 三数之和
 *
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 *
 *
 * 示例：
 *
 * 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 *
 * 满足要求的三元组集合为：
 * [
 *   [-1, 0, 1],
 *   [-1, -1, 2]
 * ]
 */
public class Leet15 {
	public static void main(String[] args) {
//		threeSum(new int[]{-1, 0, 1, 2, -1, -4});
		threeSum(new int[]{0, 0, 0});
	}

	/**
	 * 考点:思路重要,看懂后几乎一遍写出
	 */
	public static List<List<Integer>> threeSum(int[] nums) {
		List<List<Integer>> res = new ArrayList();
		if (nums == null || nums.length < 3 ) return res;
		Arrays.sort(nums);
		if(nums[0]>0 || nums[nums.length-1]<0)return res;

		for (int a = 0; a <= nums.length - 3; a++) {
			if (a > 0 && nums[a] == nums[a - 1]) {
				continue;
			}
			int b = a + 1;
			int e = nums.length - 1;
			while (b < e) {
				int sum = nums[a] + nums[b] + nums[e];

				if (sum == 0) {
					List l = new ArrayList();
					l.add(nums[a]);//Arrays.asList(,,);
					l.add(nums[b]);
					l.add(nums[e]);
					res.add(l);
//					res.add(Arrays.asList(nums[a],nums[b],nums[e]));

					//丢人,写for写出bug,
//					for (int c = b + 1; c < nums.length; c++) {
//						if (nums[c] != nums[b]) {
//							b = c;
//							break;
//						}
//					}
//					for (int d = e - 1; d >= b; d--) {
//						if (nums[d] != nums[e]) {
//							e = d;
//							break;
//						}
//					}
					//利用2个while优雅替换for,理清思路,
					//不重复,b++,e--
					do{
						b++;
					}while(b<e && nums[b]==nums[b-1]);
					do{
						e--;
					}while(b<e && nums[e]==nums[e+1]);
				} else if (sum > 0) {
					e--;
				} else {
					b++;
				}
			}
		}

		return res;
	}
	public void backTrace(int b) {

	}

}
